1. Field of the Invention
The present invention relates generally to computer implemented systems for storing and retrieving data and in particular, to a method and apparatus for delta compression floating point coordinate data
2. Description of the Related Art
Today""s software applications are often called upon to store and retrieve vast amounts of data. This is particularly so in software applications used to create art, technical drawings, schematics and the like, because these data files include data describing a large number of lines and curves. In many instances, the data file size can become quite large, in some cases exceeding the capacity of ordinary floppy disks, and requiring a substantial amount of time to read and write the data to the media
In many instances, the data to be stored or retrieved for such applications comprises a plurality of data values describing a series of closely-spaced data points expressed in Cartesian coordinates. In such cases, each data value often exhibits a high degree of correlation with data values for nearby data points. Further, as the number of data points in a given line or curve increase, the correlation between a data value for a particular data point and the next corresponding data point increase. What is needed is a simple, easy to implement method of compressing data files having inter-correlated data values. The present invention satisfies that need.
To address the requirements described above, the present invention discloses a method, apparatus, article of manufacture, and a memory structure for delta compression of floating point coordinate data. This allows the compression of sequential drawing coordinates in a file, resulting in the usage of less storage space and faster read and write access to the data.
The method begins by segmenting a first data value into common digits and non-common digits. The common digits are the digits in the first data value that have the same value as the corresponding digits in a second data value (typically, the data value preceding the first data value). A code identifying the common digits is then generated, and stored along with the common digits for later retrieval. This represents the compressed first data value.
The compressed data is decompressed by performing the steps of reading the compressed data value and the code (which identifies the digits that are common between the first data value and a second data value), and substituting the digits common between the first data value and the second data value according to the code.
In one embodiment, the non-compressed data values are drawing coordinates expressed as IEEE (Institute of Electrical and Electronic Engineers) double-precision values, stored in INTEL byte order. The (x,y) coordinates of each data point are compared to the previous data point""s (x,y) coordinates to determine whether the values have zero, two, four, or eight bytes in common. A two-bit code indicating which of these cases was encountered is written, followed by the actual bytes that are different. Because of the way IEEE double-precision values are expressed, the data values are effectively compressed when the data values are close to one another.
The apparatus comprises means for performing the method steps described above. In each case, the means for performing these steps may include, for example a computer, a special purpose processor, or a combination of computers connected via an intranet, the Internet, or similar communication path. The article of manufacture comprises a data storage device tangibly embodying instructions to perform the method steps described above.